package leetcode.offer0059;

import java.util.Deque;
import java.util.LinkedList;
import java.util.TreeMap;

public class MaxQueue {

	Deque<Integer> queue;

	TreeMap<Integer, Integer> map;

	public MaxQueue() {
		queue = new LinkedList<>();
		map = new TreeMap<>();
	}

	public int max_value() {
		if (queue.isEmpty()) {
			return -1;
		}
		return map.lastKey();
	}

	public void push_back(int value) {
		queue.add(value);
		map.put(value, map.getOrDefault(value, 0) + 1);
	}

	public int pop_front() {
		if (queue.isEmpty()) {
			return -1;
		}
		int value = queue.pollFirst();
		int size = map.get(value);
		if (size == 1) {
			map.remove(value);
		} else {
			map.put(value, size - 1);
		}
		return value;
	}
}
